فصل 11
دیکشنری ها
این فصل یک نوع داخلی^1 دیگر به نام دیکشنری را ارائه می کند. دیکشنری ها یکی از بهترین ویژگی های پایتون هستند؛ آنها زیر بنای خیلی از الگوریتم های کارآمد^2 و ظریف^3 هستند.
11. دیکشنری یک نگاشت^4 است
دیکشنری مثل یک لیست هست اما عمومی تر. در لیست ها، اندیس ها باید عدد صحیح^5 باشند؛ در یک دیکشنری آنها می توانند (تقریباً) هر نوعی باشند.
یک دیکشنری شامل مجموعه ای از اندیس هاست که به آنها کلید^6 می گوییم و مجموعه ای از مقادیر^7. هر کلید فقط به یک مقدار نسبت داده می شود. به یک کلید و یک مقدار، زوج کلید-مقدار[^8] یا گاهی به آنها آیتم^9 گفته می شود.
به زبان ریاضی، یک دیکشنری نشان دهنده یک نگاشت از کلید ها به مقدار هاست، بنابراین می توان گفت هر کلید به یک مقدار «نگاشته می شود»^10. به عنوان مثال، ما یک دیکشنری خواهیم ساخت که کلمات انگلیسی را به اسپانیایی می نگارد، بنابراین کلید ها و مقدار ها همه رشته^11 هستند.
تابع dict یک دیکشنری جدید بدون هیچ آیتی می سازد. به این دلیل که dict نام یک تابع داخلی است، نباید از آن به عنوان اسم یک متغیر استفاده کنید.
>>> eng2sp = dict()
>>> eng2sp
{}
کروشه ها، {}، یک دیکشنری خالی رو نشان می دهند. برای اضافه کردن آیتم ها به دیکشنری، می توانید از براکت استفاده کنید:
>>> eng2sp['one'] = 'uno'
این خط یک آیتم می سازد که از کلید ‘one’ به مقدار ‘uno’ می نگارد. اگر ما دیکشنری رو دوباره چاپ کنیم، یک زوج کلید-مقدار با یک دونقطه بین کلید و مقدار می بینیم:
>>> eng2sp
{'one': 'uno'}
این فرمت خروجی، یک فرمت ورودی نیز هست. برای مثال، می توانید یک دیکشنری جدید با سه آیتم بسازید:
>>> eng2sp = {'one': 'uno', 'two': 'dos', 'three': 'tres'}
اما اگر eng2sp را چاپ کنید، ممکن است قافل گیر شوید:
>>> eng2sp
{'one': 'uno', 'three': 'tres', 'two': 'dos'}
ترتیب زوج های کلید مقدار ممکن است یکسان نباشد. اگر همین مثال را در کامپیوترتان تایپ کنید، ممکن است جواب متفاوتی بگیرید. عموماً، ترتیب آیتم ها در یک دیکشنری غیر قابل پیش بینی است.
اما این مشکلی نیست، چون المان های یک دیکشنری هیچ گاه با اندیس های عدد صحیح جستجو نمی شوند. بلکه به جای آن، از کلید ها برای جستجو مقادیر متناظر استفاده می شود.
>>> eng2sp['two']
'dos'
کلید ‘two’ همیشه به مقدار ‘dos’ نگاشته می شود بنابراین ترتیب آیتم ها مهم نیست.
اگر آن کلید در دیکشنری نباشد، یک استثنا^12 می گیرید:
>>> eng2sp['four']
KeyError: 'four'
تابع len بر روی دیکشنری ها کار می کند؛ تعداد زوج های کلید مقدار را بر می گرداند.
>>> len(eng2sp)
3
عملگرin نیز بر روی دیکشنری ها کار می کند. این عملگر به شما می گوید که آیا چیزی به عنوان یک کلید در دیکشنری ظاهر شده است. (به عنوان مقدار ظاهر شدن کافی نیست).
>>> 'one' in eng2sp
True
>>> 'uno' in eng2sp
False
برای اینکه ببینید چیزی به عنوان یک مقدار در دیکشنری ظاهر شده است، می توانید از متد values استفاده کنید، که مجموعه ای از مقادیر را بر می گرداند، و سپس از عملگر in استفاده کنید.
>>> vals = eng2sp.values()
>>> 'uno' in vals
True
عملگر in از الگوریتم های متفاوتی برای لیست ها و دیکشنری ها استفاده می کند. برای لیست ها، المان های لیست را به ترتیب جستجوی می کند، مانند بخش 8.6. هر چه لیست طولانی تر باشد، زمان جستجو با نسبت مستقیم طولانی تر می شود.
برای دیکشنری ها، پایتون از الگوریتمی به نام درهم ساز^13 که خصوصیت قابل توجهی دارد: عمگر in بدون توجه به اینکه چند آیتم در دیکشنری است زمان یکسانی طول می کشد. در بخش B.4 توضیح می دهم که چگونه چنین چیزی امکان پذیر است، اما ممکن است توضیحات تا زمانی که چند فصل دیگر را نخوانید، قابل فهم نباشد.
11.2 دیکشنری به عنوان مجموعه ای از شمارنده ها
فرض کنید رشته ای به شما داده شده است و می خواهید بشمرید چند بار هر حرف تکرار شده است. راه های مختلفی برای انجام آن است:
- می توانید 26 متغیر بسازید، یکی برای هر حرف الفبا. بعد می توانید رشته را پیشمایش کنید، برای هر کاراکتر، شمارنده متناظر با آن را افزایش دهید، احتمالاً از شرط های پشت سر هم استفاده کنید.
- می توانید یک لیست با 26 المان درست کنید. بعد می توانید هر کاراکتر را به یک عدد تبدیل کنید(با استفاده از تابع داخلی ord)، از عدد به عنوان یک اندیس برای لیست استفاده کنید، و شمارنده مناسب را افزایش دهید.
- می توانید یک دیکشنری با کاراکتر ها به عنوان کلید ها و شمارنده ها به عنوان مقدار های متناظراستفاده کنید. اولین باری که یک کاراکتر را می بینید، یک آیتم به دیکشنری اضافه می کنید. بعد از آن مقدار آیتمی که وجود دارد را اضافه می کنید.
هر کدام از این گزینه ها محاسبات یکسانی را انجام می دهند، اما هر کدام این محاسبات را به روش متفاوتی پیاده سازی می کنند:
یک پیاده سازی^14 راهی برای انجام یک محاسبه^15 است؛ بعضی از پیاده سازی ها بهتر از پیاده سازی های دیگر هستند. به عنوان مثال، یک مزیت پیاده سازی دیکشنری این است که نیازی نیست که از قبل بدانیم کدام حرف ها در رشته ظاهر شده اند و فقط نیاز است که برای حرف هایی که ظاهر می شوند فضا اختصاص بدهیم.
کد مورد نظر به شکل زیر خواهد بود:
def histogram(s):
d = dict()
for c in s:
if c not in d:
d[c] = 1
else:
d[c] += 1
return d
اسم تابع histogram است، که یک اصطلاح آماری برای یک مجموعه شمارنده(یا فراوانی) است.
اولین خط تابع یک دیکشنری خالی می سازد. حلقه for رشته را می پیماید. هر بار در حلقه، اگر کاراکتر c در دیکشنری نباشد، یک آیتم جدید با کلید c و مقدار اولیه 1 می سازیم. اگر c پیش از این در دیکشنری است d[c] را افزایش می دهیم.
به اینصورت کار می کند:
>>> h = histogram('brontosaurus')
>>> h
{'a': 1, 'b': 1, 'o': 2, 'n': 1, 's': 2, 'r': 2, 'u': 2, 't': 1}
هیستوگرام نشان می دهد که حرف های ‘a’ و ‘b’ یکبار تکرار شده اند. ‘o’ دوبار ظاهر شده است و....
دیکشنری ها متدی به نام get دارند که یک کلید و یک مقدار پیش فرض می گیرد. اگر کلید در دیکشنری باشد، get مقدار متناظر را برمی گرداند. در غیر اینصورت مقدار پیش فرض را بر می گرداند. برای مثال:
>>> h = histogram('a')
>>> h
{'a': 1}
>>> h.get('a', 0)
1
>>> h.get('b', 0)
0
به عنوان تمرین، از get برای نوشتن histogram به صورت خلاصه تر استفاده کنید. باید بتوانید که دستور if را حذف کنید.
11.3 حلقه ها و دیکشنری ها
اگر از یک دیکشنری در دستور for استفاده کنید، کلید های دیکشنری را پیمایش می کند. برای مثال، print_hist هر کلید و مقدار متناظر را چاپ می کند:
def print_hist(h):
for c in h:
print(c, h[c])
خروجی به صورت زیر خواهد بود:
>>> h = histogram('parrot')
>>> print_hist(h)
a 1
p 1
r 2
t 1
o 1
دوباره، کلید ها هیچ ترتیب خاصی ندارند. دیکشنری ها متدی به نام keys دارند که کلید های دیکشنری را بدون هیچ ترتیب خاصی، به صورت یک لیست برمی گرداند. به عنوان تمرین، print_hist را تغییر دهید تا کلید ها و مقدارهای آنها را به ترتیب حروف الفبا چاپ کند.
11.4 جستجوی معکوس
با یک دیکشنری d و یک کلید k، پیدا کردن مقدار متناظر d[k] = v آسان است. این عمل یک جستجو^16 نامیده می شود.
اما اگر v را داشته باشید و بخواهید k را پیدا کنید چه می کنید؟ دو مشکل دارید: اولاً، ممکن است بیشتر از یک کلید باشد که به مقدار v نگاشته شود. بر حسب کاربرد، ممکن است که بتوانید یکی را انتخاب کنید، یا ممکن است نیاز باشد که لیستی بسازید که شامل همه آنها باشد. دوماً، هیچ ساختار ساده ای برای انجام یک جستجو مکعوس[^17] وجود ندارد. باید جستجو کنید.
تابع زیر یک مقدار می گیرد و اولین کلیدی که به آن مقدار نگاشته می شود بر می گرداند:
def reverse_lookup(d, v):
for k in d:
if d[k] == v:
return k
raise LookupError()
این تابع مثال دیگری از الگوی جستجو است، اما از ویژگی استفاده می کند که ما قبلاً ندیده ایم، raise. دستور raise یک استثنا ایجاد می کند؛ در این مورد موجب یک LookupError می شود، که یک استثنا داخلی است که برای نشان دادن شکست یک عمل جستجو، استفاده می شود.
اگر به آخر حلقه برسیم، به این معنی است که v در داخل دیکشنری به عنوان مقدار وجود ندارد، بنابراین یک استثنا بر می انگیزیم[^18].
این یک مثال از یک جستجو معکوس موفق است:
>>> h = histogram('parrot')
>>> k = reverse_lookup(h, 2)
>>> k
'r'
و یک جستجوی غیر موفق:
>>> k = reverse_lookup(h, 3)
Traceback (most recent call last):
File "<stdin>", line 1, in <module>
File "<stdin>", line 5, in reverse_lookup
ValueError
تاثیر برانگیختن استثنا به همانند زمانی است که پایتون بر می انگیزد: یک ردیابی^19 و یک پیام خطا چاپ می کند.
دستور raise می تواند یک پیام خطا دقیق به عنوان آرگومان اختیاری بگیرد. برای مثال:
>>> raise ValueError('value does not appear in the dictionary')
Traceback (most recent call last):
File "<stdin>", line 1, in ?
ValueError: value does not appear in the dictionary
یک جستجو معکوس خیلی کند تر از یک جستجو (مستقیم^20) است؛ اگر باید اغلب آن را انجام دهید، یا اگر دیکشنری بزرگ شود، کارایی برنامتان کم خواهد شد.
11.5 دیکشنری و لیست ها
لیست ها می توانند به عنوان مقدار ها در دیکشنری ها ظاهر شوند. برای مثال، اگر یک دیکشنری به شما داده شود که حرف ها را به تعداد می نگارد، شاید شما بخواهید که بر عکسش کنید؛ یعنی، بخواهید یک دیکشنری بسازید که تعداد تکرار را به حرف ها می نگارد. به این دلیل که ممکن است حرف های زیادی با تعداد تکرار یکسان باشند، هر مقدار در دیکشنری معکوس باید لیستی از حرف ها باشد.
تابع زیر یک دیکشنری را معکوس می کند:
def invert_dict(d):
inverse = dict()
for key in d:
val = d[key]
if val not in inverse:
inverse[val] = [key]
else:
inverse[val].append(key)
return inverse
هر بار در حلقه، key یک کلید از d و val مقدار متناظر آن را می گیرد. اگر val در inverse نباشد، به این معنی است که ما قبلاً آن را ندیده ایم، بنابراین، یک آیتم جدید می سازیم و با یک یگانه^21 مقدار دهی اولیه می کنیم. در غیر اینصورت ما این مقدار را قبلاً دیده ایم، بنابراین کلید متناظر با آن را به لسیت اضافه می کنیم.
به عنوان مثال:
>>> hist = histogram('parrot')
>>> hist
شکل 11.1 نمودار حالت
{'a': 1, 'p': 1, 'r': 2, 't': 1, 'o': 1}
>>> inverse = invert_dict(hist)
>>> inverse
{1: ['a', 'p', 't', 'o'], 2: ['r']}
شکل 11.1 یک نمودار حالت است که hist و inverse را نمایش می دهد. یک دیکشنری به عنوان یک جعبه با نوع type بالای آن و زوج های کلید مقدار درون آن نمایش داده شده است. اگر مقدار ها عدد صحیح هستند، اعشاری یا رشته، آنها را درون جعبه می کشم، اما معمولاً لیست ها را بیرون جعبه می کشم تا نمودار ساده باشد.
لیست ها می توانند مقدار های درون یک دیکشنری باشند، همانطور که این مثال نشان می دهد، اما نمی توانند کلید باشند. اگر امتحان کنید این اتفاق می افتد:
>>> t = [1, 2, 3]
>>> d = dict()
>>> d[t] = 'oops'
Traceback (most recent call last):
File "<stdin>", line 1, in ?
TypeError: list objects are unhashable
من قبلاً گفته ام که یک دیکشنری با استفاده از یک درهم ساز پیاده سازی می شود و آن به این معنی است که کلید ها باید قابل درهم سازی^22 باشد.
یک درهم ساز^23 تابعی است که یک مقدار(از هر نوعی) می گیرد و یک عدد صحیح برمی گرداند. دیکشنری ها از این عدد صحیح ها که به آنها مقدار درهم ساز گفته می شود برای ذخیره سازی و جستجو زوج کلید مقدار ها استفاده می کنند.
این سیستم اگر کلید ها غیر قابل تغییر^24 باشند به خوبی کار می کند. اما اگر کلید ها قابل تغییر^25 باشند، مانند لیست ها، اتفاق های بدی می افتد. برای مثال، وقتی یک زوج کلید مقدار می سازید، پایتون کلید را درهم سازی می کند و در جایگاه متناظر ذخیره می کند. اگر کلید را تغییر دهید و دوباره آن را درهم سازی کنید، به جای متفاوتی خواهد رفت. در اینصورت ممکن است دو ورودی برای کلید یکسان داشته باشید، یا ممکن است نتوانید کلید را پیدا کنید. در هر صورت، دیکشنری درست کار نخواهد کرد.
به همین دلیل است که کلید ها باید قابل درهم سازی باشند، و به همین دلیل است که نوع های قابل تغییر مانند لیست قابل درهم سازی نیستند. ساده ترین راه برای رفع این محدودیت استفاده از چندتایی^26 ها است، که در فصل بعد می بینید.
به این دلیل که دیکشنری ها قابل تغییر هستند، به عنوان کلید نمی توان از آنها استفاده کرد، اما از آنها می توان به عنوان مقدار استفاده کرد.
11.6 یادداشت ها
اگر با تابع fibonacci از بخش 6.7 کارکرده اید، ممکن است متوجه شده باشید که هر چه آرگومان بزرگتری ارائه کنید، تابع زمان طولانی تری برای اجرا خواهد گرفت. علاوه بر این، زمان اجرا به سرعت زیاد می شود.
شکل 11.2: گراف فراخوانی
برای اینکه بفهمیم چرا، شکل 11.2 را در نظر بگیرید که گراف فراخوانی[^27] را برای fibonacci با n=4 نمایش می دهد:
یک گراف فراخوانی مجموعه ای از فریم های تابع را نمایش می دهد. خط ها هر فریم تابع را به فریم های تابع هایی که فراخوانی می کند، وصل می کنند. در بالای گراف، fibonacci با n=4 تابع fibonacci با n=3 و n=2 را فراخوانی می کند. به همین منوال fibonacci با n=3 تابع fibonacci با n=2 و n=1 را فراخوانی می کند. و به همین ترتیب ادامه دارد.
بشمارید چند بار تابع های fibonacci(0) و fibonacci(1) فراخوانی می شوند. این یک راه حل ناکارامد برای این مساله است، و با بزرگ تر شدن آرگومان ها بدتر هم می شود.
یک راه حل، پیگیری متغیر های که تا حالا محاسبه شده اند با ذخیره سازی آنها در یک دیکشنری است. به یک مقدار که قبلا محاسبه شده و برای استفاده های بعدی ذخیره می شود، یادداشت^28 می گویند.
یک نسخه یادداشت گذاری شده^29 تابع fibonacci در زیر آمده است:
known = {0:0, 1:1}
def fibonacci(n):
if n in known:
return known[n]
res = fibonacci(n-1) + fibonacci(n-2)
known[n] = res
return res
known یک دیکشنری است که اعداد فیبوناتچی که ما تاکنون می دانیم را ذخیره می کند. با دو آیتم شروع می شود: 0 به 0 نگاشته می شود و 1 به 1 نگاشته می شود.
هر زمان که fibonacci فراخوانی می شود، known را چک می کند. اگر نتایج تاکنون در آنجا باشند، می تواند بلافاصله برگردد. در غیر اینصورت باید مقدار جدید را محاسبه کند، آن را به دیکشنری اضافه کند و آن را برگرداند.
اگر این نسخه fibonacci را اجرا کنید و با نسخه اصلی مقایسه کنید، می بینید که بسیار سریع تر است.
11.7 متغیر های سراسری[^30]
در مثال قبلی، known بیرون تابع تعریف شده است بنابراین متعلق به فریم خاصی به نام __main__ است. متغیر های درون __main__ گاهی سراسری خوانده می شوند به این دلیل که از هر تابعی می توان به آنها دسترسی پیدا کرد. بر خلاف متغیر های محلی، که هنگامی که تابع آنها تمام می شود، ناپدید می شوند، متغیر های سراسری از یک فراخوانی تابعی به فراخوانی تابعی دیگر باقی می مانند. مرسوم است که از متغیر های سراسری برای پرچم ها^31 استفاده شود. یعنی متغیر های بولی که (مانند پرچمی هستند که) نشان می دهند که آیا یک شرط درست است یا خیر. برای مثال، بعضی از برنامه ها از پرچمی به نام verbose استفاده می کنند تا میزان جزئیات در خروجی را کنترل کنند.
verbose = True
def example1():
if verbose:
print('Running example1')
اگر سعی کنید یک متغیر سراسری را مقدار دهی مجدد کنید، ممکن است غافلگیر شوید. از مثال پایین انتظار می رود که پیگیری کند که آیا تابع فراخوانی شده است یا خیر.
been_called = False
def example2():
been_called = True # WRONG
اما اگر اجرایش کنید، می بینید که مقدار been_called تغییر نمی کند. مشکل این است که example2 یک متغیر محلی جدید به نام been_called می سازد. متغیر محلی وقتی تابع تمام می شود از بین می رود و هیچ تاثیری بر روی متغیر سراسری ندارد.
برای مقدار دهی مجدد یک متغیر سراسری درون یک تابع باید متغیر سراسری را قبل استفاده اعلام^32 کنید.
been_called = False
def example2():
global been_called
been_called = True
دستور global به مفسر چیزی شبیه این جمله می گوید: «در این تابع، وقتی می گویم been_called، منظورم آن متغیر سراسری است، یک متغیر محلی نساز.»
یک مثال که سعی می کند یک متغیر سراسری را به روز رسانی کند:
count = 0
def example3():
count = count + 1 # WRONG
اگر اجرایش کنید خطای زیر را می گیرید:
UnboundLocalError: local variable 'count' referenced before assignment
پایتون فرض می کند که متغیر count محلی است، و با آن فرض شما قبل از نوشتن آن، آن را می خوانید. راه حل، باز، اعلام کردن count به عنوان یک متغیر سراسری است.
def example3():
global count
count += 1
اگر یک متغیر سراسری به یک مقدار تغییر پذیر^33 رجوع می کند، شما می توانید آن مقدار را بدون اعلام کردن آن متغیر تغییر دهید:
known = {0:0, 1:1}
def example4():
known[2] = 1
بنابراین شما می توانید المان های یک لیست یا دیکشنری سراسری را اضافه، حذف یا جایگزین کنید. اما اگر بخواهید متغیر را نسبت دهی مجدد کنید، باید اعلامش کنید.
def example5():
global known
known = dict()
متغیر های سراسری می توانند مفید باشند، اما اگر تعداد زیادی از آنها را داشته باشید، و مکررا آنها را تغییر دهید، ممکن است باعث شوند که اشکال زدایی^34 برنامه سخت شود.
11.8 اشکال زدایی
همینطور که با مجموعه داده های بزرگتر کار می کنید، ممکن است اشکال زدایی با چاپ کردن و چک کردن دستی خروجی، سنگین شود. چند پیشنهاد برای اشکال زدایی مجموعه داده های بزرگ:
مقیاس ورودی را کم کنید: اگر امکان دارد، سایز مجموعه داده را کم کنید. برای مثال اگر برنامه یک فایل متنی را می خواند، فقط با 10 خط اول شروع کنید، یا با کوچکترین مثالی که می توانید پیدا کنید. شما می توانید یا خود فایل ها را ویرایش کنید، یا (بهتر از آن) برنامه را به نحوی تغییر دهید که فقط n خط اول ورودی را می خواند.
اگر خطایی باشد، می توانید n را به کمترین مقداری که خطا را آشکار می کند تغییر دهید، و سپس آن را بتدریج حین یافتن و تصحیح خطا ها، زیاد کنید.
خلاصه ها و نوع ها را چک کنید: به جای چاپ کردن و چک کردن کل مجموعه داده، چاپ کردن خلاصه داده ها را در نظر بگیرید: برای مثال، تعداد آیتم های درون یک دیکشنری یا مجموع یک لیست اعداد.
یک علت شایع خطا های زمان اجرا، مقداری است که از نوع درست نیست. برای اشکال زدایی این نوع از خطا ها، معمولا چاپ کردن نوع آن مقدار کافی است.
خود بررسی^35 بنویسید: بعضی از اوقات می توانید کدی بنویسید که به صورت خودکار خطاها را چک کند. برای مثال، اگر میانگین لیستی از اعداد را حساب می کنید، می توانید چک کنید که حاصل بزرگتر از بزرگترین المان، یا کوچکتر از کوچکترین المان لیست نیست. به این روش
«بررسی سلامت»[^36] می گویند به این دلیل که نتایجی که «مشکل سلامتی»^37 دارند پیدا می کند.
نوع دیگری از بررسی، نتایج دو محاسبه متفاوت را با هم مقایسه می کند تا ببیند که آیا سازگار هستند. به این روش «بررسی سازگاری[^38]» می گویند.
خروجی را فرمت کنید: فرمت کردن خروجی، می تواند پیدا کردن خطاها را ساده تر کند. مثالی در بخش 6.9 دیدیم. ماژول pprint تابع pprint را فراهم می کند که نوع های درونی را به فرمتی که برای انسان راحتر خوانده شود نمایش می دهد. (pprint مخفف pretty print به معنی چاپ زیبا است.)
دوباره، زمانی که صرف سکوب بندی می کنید، می تواند زمانی که صرف اشکال زدایی می کنید را کاهش دهد.
11.9 واژه نامه
نگاشت: رابطه ای که هر المان یک مجموعه به یک المان یک مجموعه دیگر مربوط می شود.
دیکشنری: نگاشتی از کلید ها به مقدار های متناظر آنها.
زوج کلید-مقدار: نمایش نگاشت از یک کلید به یک مقدار.
آیتم: در یک دیکشنری، نامی دیگر برای یک زوج کلید مقدار.
کلید: شی ای که در یک دیکشنری به عنوان قسمت اول یک زوج کلید مقدار ظاهر می شود.
مفدار: شی ای که در یک دیکشنری به عنوان قسمت دوم یک زوج کلید مفدار ظاهر می شود. این استفاده از استفاده قبلی ما از کلمه «مقدار» خاص تر است.
پیاده سازی: روشی برای انجام محاسبات
جدول درهم سازی: الگوریتمی که برای ساختن دیکشنری های پایتون استفاده شده است.
تابع درهم ساز: تابعی که توسط یک جدول درهم سازی برای محاسبه مکان یک کلید استفاده می شود.
[^8]: key-value pair
[^17]: reverse lookup
[^18]: raise an exception
[^27]: call graph
[^30]: Global Variables
[^36]: sanity check
[^38]: consistency check